import java.util.ArrayList;
import java.util.List;

public class project {
    public int numberOfBeams(String[] bank) {
        int res=0;//激光的数量
        //bef前一次有激光设备的行的设备数量，cur当前行（激光设备不为0的情况）激光设备数量
        int bef=0,cur=0;
        for (int i = 0; i < bank.length; i++) {
            int tmp=0;//临时保存当前行的设备数量
            for (int j = 0; j < bank[i].length(); j++) {
                if(bank[i].charAt(j)=='1') tmp++;
            }
            if(tmp==0) continue;//如果当前行设备数量为0，则跳出本次循环
            bef=cur;
            cur=tmp;
            res=res+bef*cur;
        }
        return res;
    }




















    public String dayOfTheWeek(int day, int month, int year) {
        String[] str=new String[]{"Sunday","Monday","Tuesday","Wednesday","Thursday","Friday","Saturday"};
        int sum=4;
        int[] months=new int[]{31,28,31,30,31,30,31,31,30,31,30,31};
        if(year>1971){
            for(int i=1971;i<year;i++){
                sum+=365;
                if(i%4==0&&i%100!=0||i%400==0){
                    sum+=1;
                }
            }
        }
        for(int i=0;i<month-1;i++){
            sum+=months[i];
        }
        if(month>=3&&(year%4==0&&year%100!=0||year%400==0)){
            sum++;
        }
        sum+=day;
        return str[sum%7];
    }
























    boolean[][] dp;
    char[] ori;
    List<List<String>> res;
    public String[][] partition(String s) {
        ori = s.toCharArray();
        int len = s.length();
        dp = new boolean[len][len];
        res = new ArrayList<>();
        for(int i = 0; i < len; i++) {
            for(int j = 0; j <= i; j++) {
                if(ori[i] == ori[j] && (i - j <= 2 || dp[j + 1][i - 1]))
                    dp[j][i] = true;
            }
        }
        dfs(0, new ArrayList<>());

        String[][] ans = new String[res.size()][];
        for (int i = 0; i < res.size(); i++) {
            ans[i] = new String[res.get(i).size()];
            for (int j = 0; j < ans[i].length; j++) {
                ans[i][j] = res.get(i).get(j);
            }
        }
        return ans;
    }

    public void dfs (int depth, List<String> cur) {
        if(ori.length == depth) {
            res.add(new ArrayList<>(cur));
            return;
        }

        for(int i = depth; i < ori.length; i++) {
            if(canAdd(depth, i)) {
                cur.add(new String(ori, depth, i - depth + 1));
                dfs(i + 1, cur);
                cur.remove(cur.size() - 1);
            }
        }
    }

    public boolean canAdd(int l, int r) {
        return dp[l][r];
    }
}
